
import javax.management.RuntimeErrorException;

public class LinkedList {
    public static void main(String[] args) {
        LinkList linkList =new LinkList();
        linkList.insert(1);
        linkList.insert(2);
        linkList.insert(3);
        linkList.insert(4);
        linkList.insert(5);
        System.out.println(linkList);
        try{
            linkList.delete(3);
        }catch(Exception e){
            System.out.println(e.getMessage());
        }
        System.out.println(linkList);

        Queue queue=new Queue();
        
        Stack stack=new Stack();

        int[] array ={1,2,3,4,5,6};
        for (int i : array) {
            queue.enqueue(i);
            stack.push(i);
        }
        System.out.println(queue.linkList);
        System.out.println(stack.linkList);
        try {
            System.out.println(queue.dequeue());
            System.out.println(stack.pop());
        } catch (Exception e) {
            e.printStackTrace();
        }

    }
}

class Stack{
    LinkList linkList;
    public Stack(){
        this.linkList=new LinkList();
    }
    void push(int x){
        linkList.insert(x);
    }

    int pop() throws Exception{
        if(isEmpty()){
            throw new Exception("stack is empty");
        }
        int x = linkList.nil.next.key;
        linkList.delete(x);
        return x;
    }

    boolean isEmpty(){
        return linkList.isEmpty();
    }
}

class Queue{
    LinkList linkList;
    public Queue(){
        this.linkList=new LinkList();
    }

    void enqueue(int key){
        linkList.insert(key);
    }
    int dequeue() throws Exception{
        if(isEmpty()){
            throw new Exception("Queue is empty");
        }
        int key = linkList.nil.prev.key;
        linkList.delete(key);
        return key;
    }

    boolean isEmpty(){
        return linkList.isEmpty();
    }
}

//环形双向链表
class LinkList{
    //哨兵节点
    Node nil;
    public LinkList(){
        nil=new Node(-1);
        nil.next=nil.prev=nil;
    }
    // 插入新的元素将建立四条连接
    void insert(int key){
        Node n=new Node(key);
        //先建立后面的两条链接，目的是不要覆盖掉nil.next
        n.next=nil.next;
        nil.next.prev=n;

        nil.next=n;
        n.prev=nil;
    }
    // 删除一个元素将建立两条连接
    void delete(int key){
        Node x= search(key);

        // 假设是a，b，c，删除b，b.next=c,b.prev=a;
        x.prev.next=x.next;
        x.next.prev=x.prev;
    }

    Node search(int key){
        if(isEmpty()) return null;
        Node x=nil.next;
        while(x!=nil && x.key!=key){
            x=x.next;
        }
        if(x==nil){
            return null;
        }
        return x;
    }

    public String toString(){
        if(isEmpty()) return null;
        Node x =nil.next;
        String s=" ";
        while(x!=nil){
            s+=x.key+" ";
            x=x.next;
        }
        return s;
    }
    boolean isEmpty(){
        return nil.next==nil;
    }
}
class Node{
    int key;
    Node prev;
    Node next;
    public Node(int key){
        this.key=key;
        prev=next=null;
    }
}
